<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>Document</title>
  </head>
  <body>
    <!-- 使数组严格递增 -->
    <script>
      /*
        思路：
        - 对 arr2 进行去重和排序，以便在后续二分查找中使用。
      - 在 arr1 的两端各添加一个边界值，分别为负无穷和正无穷，方便后续处理边界情况。
      - 定义长度为 N 的数组 dp ，其中 dp[i] 表示将 arr1 中前 i 个元素转化为严格递增数组所需的最小操作数。
      - 初始化 dp[0] 为 0 ，表示前 0 个元素已经是严格递增数组。
      - 从 i=1 开始遍历 arr1 ：
      - 如果 arr1[i - 1] < arr1[i] ，说明第 i 个元素已经大于等于前一个元素，不需要额外的操作，因此 dp[i] = dp[i - 1] 。
      - 否则，需要在 arr2 中选择一个元素来替换 arr1[i] ，使得前 i 个元素仍然构成一个严格递增数组。因为 arr2 已经排序，
      可以使用二分查找来找到一个最大的 arr2[idx] ，使其小于等于 arr1[i] 。然后在倒数第二个元素往前最多选择 idx 个元素进行替
      换，其它元素不能更改，保持其原有的顺序。因此需要遍历 j,min(i-1,idx) ，计算出选择 j 个元素进行替换所需的操作数 dp[i-j-1]+j ，取其中的最小值，更新 dp[i] 。
      - 定义一个函数 search ，用于在 arr2 中进行二分查找。返回最大的 arr2[idx] ，使其小于等于 target 。如果不存在，则返回 arr2.length 。
      - 最后返回 dp[N-1] ，若其仍为 Infinity ，则说明无法将 arr1 转化为严格递增数组，返回 -1 。
      */
      var makeArrayIncreasing = function (arr1, arr2) {
        // 因为只需要考虑操作数, 不需要考虑索引具体位置, 并且保证 arr1 严格递增, 那么 arr2 每个元素只会使用一次, 对 arr2 去重后进行排序
        arr2 = Array.from(new Set(arr2)).sort((a, b) => a - b)
        // 向前向后添加一个数字 (重点), 来保证可以得到严格递增
        arr1 = [-1, ...arr1, Infinity]
        const N = arr1.length
        // dp 定义为从 [0, i) 的严格递增的最小操作数, 注意并不包括 i
        const dp = Array(N).fill(Infinity)
        // 初始化
        dp[0] = 0
        for (let i = 1; i < N; i++) {
          if (arr1[i - 1] < arr1[i]) dp[i] = dp[i - 1]
          // 关键在于每一个值都需要判断是否需要替换
          const idx = search(arr1[i])
          // Math.min(idx, i - 1) 应该理解为限制替换的次数, 因为替换是要从 [0,i) 与 [0, idx] 进行
          // j 的意义就是 [0, i) 中替换了 j 次
          for (let j = 1; j <= Math.min(i - 1, idx); j++) {
            // 已经确定了 arr1 的替换位置, 也确定了 arr2 找到满足题意元素的位置
            // 那么从两个确定位置向左同时查找 j 步, 然后再比较arr1与arr2元素是否存在相同关系
            // 因为 arr1 要保证严格递增, 并且 arr2 通过预处理已经去重加排序, 也是严格递增
            // 如果满足条件那么就直接进行批量替换, 然后在比较 dp 的值
            if (arr1[i - 1 - j] < arr2[idx - j]) dp[i] = Math.min(dp[i], dp[i - j - 1] + j)
          }
        }
        function search(target) {
          let left = 0
          let right = arr2.length
          while (left < right) {
            let mid = (left + right) >> 1
            if (arr2[mid] >= target) {
              right = mid
            } else {
              left = mid + 1
            }
          }
          return left
        }
        // 如果最后一个稳定为 Infinity, 那么说明无法操作
        return dp[N - 1] >= Infinity ? -1 : dp[N - 1]
      }
      console.log(makeArrayIncreasing([1, 5, 3, 6, 7], [4, 3, 1]))
    </script>
  </body>
</html>
